iT邦幫忙

2021 iThome 鐵人賽

DAY 1
1
Software Development

圖論與演算法之間的相互應用系列 第 1

圖論與演算法之間的相互應用

  • 分享至 

  • xImage
  •  

Disclaimer: 今年大概撐不到連續 30 天...大概能寫多少就是多少吧 哈哈

1 圖論為什麼重要

1.1 圖論可以幫助你看清問題的本質

圖 (Graph) 是一種抽象的數學模型,它可以用來描述東西與東西之間的關聯。這個『東西』根據想要解決的問題而定,可以有很多意義。而圖論 (Graph Theory) 便是一類將事物簡化成『東西』與『關聯』的模型之後,針對其結構和性質而得出的一套數學理論。

https://ithelp.ithome.com.tw/upload/images/20210915/20112376POLu7GJH1Z.png

https://ithelp.ithome.com.tw/upload/images/20210915/20112376c9pswJBj5x.png

圖一:上面繪製的兩張圖,都是有 6 個點的完全圖,他們雖然看起來不太一樣,但是結構相同:任何兩個點之間都連有一條邊。

1.2 資訊科學裡面哪裡有圖論

簡短的答案:到處都是。比方說最直接的網路模型(設備與設備之間的資料傳輸連結),我們可以利用化簡後的圖論模型找出伺服器流量的瓶頸在哪裡、也可以設計出當某些機器過載的時候資料該如何繞道而行。在非傳統關聯式資料庫 (NoSQL) 中,也有一些專門為稀疏關聯設計出的圖論資料庫模型,比方說 GraphQL 等,在查詢與存儲資料的效能中,比起傳統的關聯式資料庫更能獲得一些優勢。在編譯器的最佳化過程中,也會對如控制流圖和資料流圖等等進行分析,讓該程式編譯後執行效率得以提升。此外,有一些產品天生就與圖論有關,比方說地圖的自動導航功能:該如何引導使用者用最快速度抵達目的地;在倉儲和物流系統中,資源和貨品該如何調度;影像和圖像的匹配與修改,也可以透過圖論模型來設計演算法。

1.x 冷笑話

如果你寫了一份程式碼,放了很久很久,它就會變成一張圖了。為什麼?因為老碼是圖啊...

2 這個系列文打算分享什麼

會用到圖論的常見演算法問題當中的理論和解法。圖論的應用層面有兩種,其中一種應用是把一個題目使用圖論的模型來找出其特性,並且根據這些特性設計出演算法解決該問題。另一種應用則是建立圖論模型後,使用已知的工具(比方說線性規劃、矩陣相乘等等)來解決這些已知的圖論問題。我相信有些朋友會想知道關於 Leetcode 上面的圖論題目要怎麼解,所以如果剛好有涵蓋到相關內容的話,我也會用 Leetcode 的題目作為舉例,這樣大概會有心理上比較踏實的感覺。

如果真的要說實作的技術成分的話,藉由這 30 天,我這次想要學學用 python 的 networkx 這個 package 練習畫圖。


下一篇
圖的資料結構
系列文
圖論與演算法之間的相互應用30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言